Theory of Computation
Q51.
Which of the following languages is generated by the given grammar? S\rightarrow aS|bS|\varepsilonQ52.
Consider the following statements about the context free grammarG=\{S \rightarrow S S, S \rightarrow a b, S \rightarrow b a, S \rightarrow \epsilon\}I. G is ambiguous II. G produces all strings with equal number of a's and b's III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?Q54.
Consider the following context-free grammar over the alphabet \sum = {a,b,c} with S as the start symbol. S\rightarrowabScT|abcT T\rightarrowbT|b Which one of the following represents the language generated by the above grammar ?Q55.
Consider the following expression grammar G: E\rightarrowE-T|T T\rightarrowT+F|F F\rightarrow(E)|id Which of the following grammars is not left recursive, but is equivalent to G?Q56.
A CFG (Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form \mathrm{A} \rightarrow \mathrm{BC} or \mathrm{A} \rightarrow \mathrm{a}. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is:Q57.
Consider the following context-free grammars: G1: S\rightarrowaS|B, B\rightarrowb|bB G2: S\rightarrowaA|bB, A\rightarrowaA|B|\varepsilon, B\rightarrowbB|varepsilon Which one of the following pair of languages is generated by G1 and G2, respectively?Q58.
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.\begin{array}{l} S \rightarrow a S \mid A \\ A \rightarrow a A b|b A a| \epsilon \end{array}For the string "aabbaab" how many steps are required to derive the string and how many parse trees are there?Q60.
Consider a CFG with the following productions. S \to AA \mid B A \to 0A \mid A0 \mid 1 B \to 0B00 \mid 1 S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is: